#include<iostream>
#include<map>
using namespace std;


// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

// 随机链表的复制
class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> ndmp;
        // 原链表的基本复制
        Node *copyhead, *copytail;
        copyhead = copytail = nullptr;
        Node* cur = head;
        while (cur) {
            if (copytail == nullptr)
                copyhead = copytail = new Node(cur->val);
            else {
                Node* newnode = new Node(cur->val);
                copytail->next = newnode;
                copytail = copytail->next;
            }
            // 建立原链表与拷贝链表的联系
            ndmp[cur] = copytail;

            cur = cur->next;
        }
        // random的连接
        cur = head;
        while (cur) {
            if (cur->random == nullptr) {
                ndmp[cur]->random = nullptr;
            } else {
                ndmp[cur]->random = ndmp[cur->random];
            }

            cur = cur->next;
        }
        return copyhead;
    }
};

int main()
{

	return 0;
}
